// Selection implementation
// Copyright 2006 (C) Ralph Thomas

#include <toolkit/selection.h>
#include <iostream>

namespace toolkit {

	template<typename IdType>
	inline adobe::any_regular_t value_from_type(IdType t) { return adobe::any_regular_t(t); }
	template<typename IdType>
	bool ltpair_2nd( const std::pair<int, IdType>& lhs, const std::pair<int, IdType>& rhs ) {
		return lhs.second < rhs.second;
	}
	template<typename IdType>
	struct sort_selection_t {
		typedef std::pair<int, IdType>			index_id_mapping_t;
		typedef std::vector<index_id_mapping_t>	index_id_map_t;
		typedef std::vector<IdType>				id_list_t;
		index_id_map_t&	reference_m;
		
		sort_selection_t( index_id_map_t& ref ) : reference_m( ref ) {}
		bool operator()( IdType lhs, IdType rhs ) {
			//
			// We're sorting by index in the reference (index is the
			// first part of the pair.
			//
			typename index_id_map_t::iterator lhs_lb = std::lower_bound(reference_m.begin(), reference_m.end(), index_id_mapping_t(0, lhs), &ltpair_2nd<IdType>);
			typename index_id_map_t::iterator rhs_lb = std::lower_bound(reference_m.begin(), reference_m.end(), index_id_mapping_t(0, rhs), &ltpair_2nd<IdType>);
			return lhs_lb->first < rhs_lb->first;
		}
	};
	template<typename IdType>
	struct selection_exists_t {
		typedef std::pair<int, IdType>			index_id_mapping_t;
		typedef std::vector<index_id_mapping_t>	index_id_map_t;
		typedef std::vector<IdType>				id_list_t;
		index_id_map_t&	reference_m;
		
		selection_exists_t( index_id_map_t& ref ) : reference_m( ref ) {}
		//
		// Note: we actually return true if the selection doesn't exist
		// in the universe, because the only time this struct gets used is
		// for remove_if.
		//
		bool operator()( IdType t ) {
			return !std::binary_search(reference_m.begin(), reference_m.end(), index_id_mapping_t(0, t), &ltpair_2nd<IdType>);
		}
	};
	template<typename IdType> inline IdType default_value() { return IdType(); }
	template<> inline int default_value<int>() { return -1; }
	//
	/// This class manages a selection. It is optimized for managing
	/// selections where the type that is being selected (typically
	/// some kind of id) is LessThanComparable.
	///
	/// This class also implements Adobe Lightroom-style selection where
	/// if there is a multiple selection we don't lose it for clicks
	/// inside the selection -- this lets us open a multiple selection
	/// with a double click.
	//
	template <typename IdType> struct selection_impl_t : public selection_t {
		selection_impl_t(const adobe::any_regular_t& universe_pump, adobe::sheet_t& sheet) : primary_m(default_value<IdType>()), datapump_m(sheet) {
			datapump_m.initialize( universe_pump, boost::bind( &selection_impl_t<IdType>::update_universe, this, _1 ), 0 );
		}
		~selection_impl_t() {}

		adobe::any_regular_t get_primary() {
			if (primary_m == default_value<IdType>()) return adobe::any_regular_t();
			return adobe::any_regular_t(primary_m);
		}
		unsigned int get_index(const adobe::any_regular_t& v) {
			IdType t = v.cast<IdType>();
			typename index_id_map_t::const_iterator i = std::lower_bound(index_id_map_m.begin(), index_id_map_m.end(), index_id_mapping_t(0, t), &ltpair_2nd<IdType>);
			if (i == index_id_map_m.end()) return 0;
			return i->first;
		}
		void toggle(const adobe::any_regular_t& value) {
			//
			// This doesn't touch the primary.
			//
			IdType t = value.cast<IdType>();
			if (std::binary_search(sorted_selected_items_m.begin(), sorted_selected_items_m.end(), t)) {
				//
				// It's set, we need to unset it.
				//
				typename id_list_t::iterator i = std::lower_bound(sorted_selected_items_m.begin(), sorted_selected_items_m.end(), t);
				sorted_selected_items_m.erase(i);
				//
				// XXX: Performance; we could look this up using
				// XXX: the existing order.
				//
				i = std::find(selected_items_m.begin(), selected_items_m.end(), t);
				selected_items_m.erase(i);
				call_monitor(t, state(t));
				return;
			}
			//
			// Set it.
			//
			set_state(get_index(value), kPartial);
		}
		void select_all() {
			selected_items_m.clear();
			sorted_selected_items_m.clear();
			selected_items_m = sorted_selected_items_m = *id_list_m;
			std::sort(sorted_selected_items_m.begin(), sorted_selected_items_m.end());
			call_monitor_all();
			call_next_and_previous();
		}
		void unselect_all() {
			primary_m = default_value<IdType>();
			for( typename monitor_map_t::const_iterator i = monitors_m.begin(); i != monitors_m.end(); i++ )
				(i->second)(kUnselected);
			selected_items_m.clear();
			sorted_selected_items_m.clear();
			call_monitor_all();
			call_next_and_previous();
		}
		void set_state(unsigned int index, selected_state_t s) {
			set_state_impl((*id_list_m)[index], s);
		}
		void set_state(const adobe::any_regular_t& v, selected_state_t s) {
			set_state_impl(v.cast<IdType>(), s);
		}
		void select_range(unsigned int start, unsigned int end) {
			//
			// Make sure we always iterate in the right way.
			//
			if (start > end) std::swap(start, end);
			//
			// This function is similar to calling set_state many times, but is
			// more efficient (it avoids performing multiple insertion sorts).
			// It works like this:
			//
			//  1. Insert all of the values into sorted_selected_items_m and
			//     into selected_items_m.
			//  2. Sort both of those lists.
			//  3. Remove duplicates.
			//
			IdType t;
			for (unsigned int i = start; i < end; i++) {
				t = (*id_list_m)[i];
				sorted_selected_items_m.push_back(t);
				selected_items_m.push_back(t);
			}
			//
			// Now sort.
			//
			std::sort(sorted_selected_items_m.begin(), sorted_selected_items_m.end());
			sort_selection_t<IdType> selection_comp(index_id_map_m);
			std::sort(selected_items_m.begin(), selected_items_m.end(), selection_comp);
			//
			// Now clean up duplicates.
			//
			sorted_selected_items_m.erase(std::unique(sorted_selected_items_m.begin(), sorted_selected_items_m.end()), sorted_selected_items_m.end());
			selected_items_m.erase(std::unique(selected_items_m.begin(), selected_items_m.end()), selected_items_m.end());
			//
			// Finally notify everybody of the changes.
			//
			call_monitor_all();
			call_next_and_previous();
		}
		selected_state_t is_selected(unsigned int index) {
			IdType t = (*id_list_m)[index];
			if (t == primary_m) return kSelected;
			return (std::binary_search(sorted_selected_items_m.begin(), sorted_selected_items_m.end(), t)) ? kPartial : kUnselected;
		}
        void set_primary (unsigned int index) {
            if (index > id_list_m->size()) return;
            set_primary(adobe::any_regular_t((*id_list_m)[index]));
        }
		void set_primary (const adobe::any_regular_t& v) {
			//
			// This is a bit like hit, except:
			//
			//  - If the primary is within the current selection then it does a hit unexclusive
			//  - Otherwise it does a hit exclusive.
			//
			IdType t = v.cast<IdType>();
			if (std::binary_search(sorted_selected_items_m.begin(), sorted_selected_items_m.end(), t))
				set_state(v, kSelected);
			else {
				unselect_all();
				set_state(adobe::any_regular_t(t), kSelected);
			}
		}
		void monitor (const adobe::any_regular_t& v, const monitor_t& monitor ) {
			try {
				IdType t = v.cast<IdType>();
				monitors_m[t] = monitor;
				call_monitor(t, state(t));
			} catch( std::exception& ex ) {
				std::cout << "Exception monitoring value: " << v.type().name() << std::endl;
			}
		}
		void unmonitor (const adobe::any_regular_t& v) {
			typename monitor_map_t::iterator i = monitors_m.find(v.cast<IdType>());
			if( i == monitors_m.end() ) return;
			monitors_m.erase(i);
		}
		connection_t monitor_all(const monitor_all_t& monitor) {
			monitor(adobe::any_regular_t(cow_vector_t(selected_items_m)));
			return monitor_all_m.connect(monitor);
		}
		connection_t monitor_next(const monitor_value_t& next) {
			connection_t c(next_m.connect(next));
			call_next_and_previous();
			return c;
		}
		connection_t monitor_prev(const monitor_value_t& prev) {
			connection_t c(prev_m.connect(prev));
			call_next_and_previous();
			return c;
		}
		connection_t monitor_primary(const monitor_value_t& primary) {
			primary(adobe::any_regular_t(primary_m));
			return monitor_primary_m.connect(primary);
		}
	  private:
		typedef std::pair<int, IdType>			index_id_mapping_t;
		typedef std::vector<index_id_mapping_t>	index_id_map_t;
		typedef std::vector<IdType>				id_list_t;
		typedef std::map<IdType, monitor_t>		monitor_map_t;
		typedef typename util::cow_vector<IdType>::type cow_vector_t;

		void call_monitor(IdType t, selected_state_t s) {
			typename monitor_map_t::iterator i = monitors_m.find(t);
			if( i == monitors_m.end() ) return;
			i->second(s);
		}

		void call_monitor_all() {
			//
			// Notify whoever is watching all changes that we changed.
			//
			monitor_all_m(adobe::any_regular_t(cow_vector_t(selected_items_m)));
		}

		void call_next_and_previous() {
			if (selected_items_m.size() < 2) {
				//
				// We have to go outside of the selection.
				//
				unsigned int current_index = 0;
				//
				// If we can't find the primary in the selection
				// then there is no next or previous.
				//
				typename index_id_map_t::const_iterator i = std::lower_bound(index_id_map_m.begin(), index_id_map_m.end(), index_id_mapping_t(0, primary_m), &ltpair_2nd<IdType>);
				if (i == index_id_map_m.end() || i->second != primary_m) {
					next_m(adobe::any_regular_t(default_value<IdType>()));
					prev_m(adobe::any_regular_t(default_value<IdType>()));
					return;
				}
				//
				// Now from this iterator we can take the index
				// of the selected item into the original list.
				//
				current_index = i->first;
				if ((current_index > 0) && (current_index < id_list_m->size()))
					prev_m(adobe::any_regular_t((*id_list_m)[current_index - 1]));
				else
					prev_m(adobe::any_regular_t());
				current_index++;
				if (current_index < id_list_m->size())
					next_m(adobe::any_regular_t((*id_list_m)[current_index]));
				else
					next_m(adobe::any_regular_t());
				return;
			}
			//
			// We are moving inside the selection. This is a bit harder
			// because we don't have a map of index in selected_item_m
			// from value. We might be able to track the index of the
			// primary selection, but currently we don't do that.
			//
			typename id_list_t::const_iterator i = std::find(selected_items_m.begin(), selected_items_m.end(), primary_m);
			if (i == selected_items_m.end()) {
				next_m(adobe::any_regular_t());
				prev_m(adobe::any_regular_t());
				return;
			}
			typename id_list_t::const_iterator next(i);
			typename id_list_t::const_iterator prev(i);
			next++;
			prev--;
			if (i == selected_items_m.begin()) {
				prev_m(adobe::any_regular_t());
				next_m(adobe::any_regular_t(*next));
				return;
			}
			prev_m(adobe::any_regular_t(*prev));
			if (next == selected_items_m.end())
				next_m(adobe::any_regular_t());
			else
				next_m(adobe::any_regular_t(*next));
		}

		void update_universe(const adobe::any_regular_t& val) {
			if (val.type() != typeid(cow_vector_t)) return;
			//
			// The set of items that we may pick a selection from
			// has changed. We need to rebuild our id -> index map.
			//
			id_list_m = val.cast<cow_vector_t>();
			index_id_map_m.clear();
			index_id_map_m.reserve(id_list_m->size());
			for( unsigned int i = 0; i < id_list_m->size(); i++ ) {
				index_id_map_m.push_back(index_id_mapping_t(i, (*id_list_m)[i]));
			}
			std::sort(index_id_map_m.begin(), index_id_map_m.end(), &ltpair_2nd<IdType>);
			//
			// We need to prune the selection so that we don't have any
			// items selected that aren't in the current universe. This
			// is going to be *SLOW* -- we use a binary search to see if
			// the item exists, so this is O(m log(n)) where m = #selected items
			// and n = #items in universe.
			//
			// Because we could be calling the comparison function so many
			// times it's a struct rather than a boost::bind to avoid that
			// overhead.
			//
			selection_exists_t<IdType> selection_exists(index_id_map_m);
			typename id_list_t::iterator i = std::remove_if(sorted_selected_items_m.begin(), sorted_selected_items_m.end(), selection_exists);
			if (i != sorted_selected_items_m.end() ) sorted_selected_items_m.erase( i, sorted_selected_items_m.end() );
			selected_items_m = sorted_selected_items_m;
			//
			// Now that our index_id_map is in the right order, we need
			// to update our ordered_selection.
			//
			sort_selection_t<IdType> selection_comp(index_id_map_m);
			std::sort(selected_items_m.begin(), selected_items_m.end(), selection_comp);
			//
			// See if the primary selection is in the remaining selected
			// items.
			//
			if (!std::binary_search(sorted_selected_items_m.begin(), sorted_selected_items_m.end(), primary_m)) {
				IdType previous_primary = primary_m;
				if (sorted_selected_items_m.empty())
					primary_m = default_value<IdType>();
				else primary_m = selected_items_m[0];
				call_monitor(previous_primary, state(previous_primary));
				call_monitor(primary_m, kSelected);
				monitor_primary_m(adobe::any_regular_t(primary_m));
			}
			call_next_and_previous();
		}

		void set_state_impl(IdType t, selected_state_t s) {
			typename id_list_t::iterator i;
			//
			// Is it selected already?
			//
			if (!std::binary_search(sorted_selected_items_m.begin(), sorted_selected_items_m.end(), t)) {
				if (s != kUnselected) {
					i = std::upper_bound(sorted_selected_items_m.begin(), sorted_selected_items_m.end(), t);
					sorted_selected_items_m.insert(i, t);
					sort_selection_t<IdType> selection_comp(index_id_map_m);
					i = std::upper_bound(selected_items_m.begin(), selected_items_m.end(), t, selection_comp);
					selected_items_m.insert(i, t);
				}
			} else if (s == kUnselected) {
				//
				// It's selected and we need to remove it.
				//
				i = std::lower_bound(sorted_selected_items_m.begin(), sorted_selected_items_m.end(), t);
				sorted_selected_items_m.erase(i);
				sort_selection_t<IdType> selection_comp(index_id_map_m);
				i = std::lower_bound(selected_items_m.begin(), selected_items_m.end(), t, selection_comp);
				selected_items_m.erase(i);
				if (primary_m == t) primary_m = default_value<IdType>();
			}
			if (s == kSelected) primary_m = t;
			monitor_primary_m(adobe::any_regular_t(primary_m));
			call_monitor(t, state(t));
			call_monitor_all();
			call_next_and_previous();
		}
		selected_state_t state(IdType t) {
			if( t == primary_m ) return kSelected;
			if( std::binary_search(sorted_selected_items_m.begin(), sorted_selected_items_m.end(), t) ) return kPartial;
			return kUnselected;
		}

		typedef boost::signal<void (const adobe::any_regular_t&)> monitor_signal_t;

		IdType					primary_m;
		monitor_map_t			monitors_m;
		index_id_map_t			index_id_map_m;
		id_list_t				selected_items_m;
		id_list_t				sorted_selected_items_m;
		cow_vector_t			id_list_m;
		adobe::binder_helper_t	datapump_m;
		monitor_signal_t		monitor_all_m;
		monitor_signal_t		next_m;
		monitor_signal_t		prev_m;
		monitor_signal_t		monitor_primary_m;
	};

	adobe::any_regular_t make_string_selection(const adobe::array_t& name_of_universe, adobe::sheet_t& sheet) {
		return adobe::any_regular_t(selection_ptr_t(new selection_impl_t<std::string>( name_of_universe.at(0), sheet )));
	}

	adobe::any_regular_t make_int_selection(const adobe::array_t& name_of_universe, adobe::sheet_t& sheet) {
		return adobe::any_regular_t(selection_ptr_t(new selection_impl_t<int>( name_of_universe.at(0), sheet )));
	}
}

